class Solution
{
public:
    typedef pair<int, int> PII;
    // 如果使用纯暴力算法进行模拟，时间复杂度将会是O(n^3)
    // 枚举（O(n^2)）*O(n)[判断是否是回文序列]
    PII is_palindrome(const string &s, int left, int right)
    {
        while (left >= 0 && right < s.size() && s[left] == s[right])
            --left, ++right;
        return {left + 1, right - left - 1};
    }
    string longestPalindrome(string s)
    {
        // 分别以每个点为中心，向外扩展
        int begin = 0, len = 1;
        for (int i = 0; i < s.size() - 1; ++i)
        {
            PII odd = is_palindrome(s, i, i);
            if (odd.second > len)
                begin = odd.first, len = odd.second;
            PII even = is_palindrome(s, i, i + 1);
            if (even.second > len)
                begin = even.first, len = even.second;
        }
        return s.substr(begin, len);
    }
};